1. Field of the Invention
The present invention relates generally to a communication system and, in particular, to an improved bit mapping method and apparatus for a communication system.
2. Description of the Related Art
In a wireless communication system, the data generated at a source is transmitted after being subject to signal processing, which may include source coding, channel coding, interleaving, modulation, and further suitable steps. The signal received at a destination is subject to signal processing, which may include demodulation, deinterleaving, channel decoding, and source decoding, and further suitable steps.
Typically, the signal transmitted over the air is likely to be distorted by noise and fading effects of the channel and Inter-Symbol Interference (ISI).
Particularly in the high speed digital communication systems (such as next generation mobile communication systems, digital broadcast systems, broadband Internet access systems), overcoming these noise, fading, and ISI problems is one of the significant issues to fulfill the high data rate and reliability requirements. Channel coding and interleaving are well-known techniques to provide protection from error.
Interleaving is a technique to arrange data in a non-contiguous manner to avoid burst errors while passing through fading channels, thereby protecting the data from errors. Interleaving also increases the coding efficiency.
Channel coding is a technique to overcome transmission errors over a noisy and fading channel such to a destination node to improve the communication reliability. Due to their error correction functionality, the codes using in channel coding are referred to as Error Correction Codes (ECC). In order to improve the error correction capability, various types of error correction codes are proposed and under development.
Well-known error correction codes include a block code, a convolutional code, a turbo code, a Low Density Parity Check (LDPC) code, and so forth. The embodiments of the present invention to be described hereinafter make use of the LDPC code. Accordingly, a brief description is now given of prior art LDPC codes.
Although not guaranteed, the LDPC code is known to be able to minimize the transmitted signal loss. The LDPC code invented in the early 1960's is a forward error correction code that exhibits properties close to the Shannon limit.
Soon after the invention of the LDPC codes, they were forgotten due to their implementation complexity that surpassed the technology at that time. As the use LDPC code has been rediscovered since 1996 with the advance of information and communication technologies, extensive research has been conducted to determine the characteristics and methods for creating LDPC codes available with iterative decoding without compromising complexity. Recently, the LDPC code has become as an excellent error correction code appropriate for the next generation wireless communication systems along with the turbo code.
The LDPC code is usually represented by a bipartite graph, and its characteristics can be analyzed using the methods based on the graph theory, algebra, and probability theory. Typically, a graph model of a channel code is useful for describing a code. When information on an encoded bit corresponds to a vertex in a graph and the relation between encoded bits corresponds to an edge (i.e. a line segment), the graph model of the channel code may be considered as a communication network in which vertexes exchange predetermined messages through edges, thereby deriving a natural decoding algorithm. For instance, a decoding algorithm derived from a trellis, which may be considered a type of graph, includes a well-know Viterbi algorithm and a Bahl, Cocke, Jelinek, and Raviv (BCJR) algorithm.
Typically, the LDPC code is defined by a parity-check matrix and can be represented by a bipartite graph commonly referred to as a Tanner graph. In the bipartite graph, vertexes are divided into two different types. The LDPC code is represented by the bipartite graph formed by vertexes referred to as “variable node” and “check node.” A variable node corresponds to an encoded bit.
FIG. 1 is a diagram illustrating a parity check matrix of an LDPC code having the codeword length of 8, and FIG. 2 is a diagram illustrating a Tanner graph corresponding to the parity check matrix of FIG. 1.
The description of an LDPC code represented by a graph is described with reference to FIGS. 1 and 2.
Referring to FIG. 1, 8 rows of the parity check matrix means that the LDPC code generates a codeword having the length of 8, and each column corresponds to the encoded 8 bits.
Referring to FIG. 2, the Tanner graph representing the LDPC code has 8 variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and 4 check nodes 218, 220, 222, and 224. The ith column and ith row of the parity check matrix H1 of the LDPC code correspond to the variable node xi and the jth check node, respectively. If the element position at the place where the ith column and the jth row of the parity check matrix H1 of the LDPC code is 1, i.e. non-zero, this means that there exists an edge between the variable node xi and the jth check node in the Tanner graph as shown in FIG. 2.
The degree of each variable node or check node in the Tanner graph of the LDPC code means the number of edges of the node, and the number of edges of the node is equal to the number of non-zero elements on the column or row to which the corresponding element belongs in the parity-check matrix H1 of the LDPC code. Accordingly, in FIG. 2, the degrees of the variable nodes 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and the degrees of the check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5. Also, the numbers of nonzero elements of the columns or rows to which the respective elements corresponding to the variable nodes are identically 4, 3, 3, 3, 2, 2, 2, and 2; and the numbers of nonzero elements of the column or row to which the elements corresponding to the check nodes are identically 6, 5, 5, and 5.
As described above, each coded bit is mapped to a corresponding column of the parity check matrix and a corresponding variable node of the Tanner graph. The degree of each variable node corresponding to the coded bit is also referred to as a degree of coded bit.
The LDPC code is characterized in that a code word bit having a high degree is superior to a code word bit having a low degree in decoding performance. This means that the high degree variable node can acquire much information through more iterative decoding steps as compared to the low degree variable node, resulting in superior decoding performance.
A description of the signal constellation of Quadrature Amplitude Modulation (QAM), as a high degree modulation scheme typically used in wireless communication, is described hereinafter. In the QAM, the modulated symbol is composed of a real part and an imaginary part and is defined by the sizes of the real and imaginary parts with different signs. Prior to explaining the characteristics of the QAM, a Quadrature Phase Shift Keying (QPSK) modulation scheme will be described.
FIG. 3A is a diagram illustrating a Quadrature Phase Shift Keying (QPSK) signal constellation.
In FIG. 3A, a QPSK symbol represents two bits of input data. The y0 determines the sign of the real part, and y1 determines the sign of the imaginary part. That is, if the y0 is 0, the real part has the plus sign (+) and, otherwise, if the y0 is 1, the real part has the minus sign (−). Also, if y1 is 0, the imaginary part has the plus sign (+) and, otherwise, if the y1 is 1, the imaginary part has the minus sign (−). Since the y0 and y1 are the sign bits, the error probabilities of the y0 and y1 are identical with each other. In the y0,q and y1,q, q is an index indicating the qth symbol.
FIG. 3B is a diagram illustrating a 16-QAM signal constellation.
In FIG. 3B, a 16-QAM symbol represents 4 bits of input data (y0, y1, y2, and y3). The y0 and y2 bits determine the sign and size of the real part respectively, and the y1 and y3 bits determine the sign and size of the imaginary part. That is, the y0 and y1 bits determine the signs of the real and imaginary parts, and the y2 and y3 bits determine the sizes of the real and imaginary parts. Since it is easier to determine the sign of a signal than to determine the size of the signal, the error probabilities of the y2 and y3 are higher than those of the y0 and y1. Accordingly, the non-error probability or reliability of the bits can be expressed as R(y0)=R(y1)>R(y2)=R(y3). Here, R(y) denotes the reliability of y bit. Unlike the QPSK, the bits (y0, y1, y2, and y3) constituting the QAM symbol have different reliabilities.
In 16-QAM, two bits among the 4 bits constituting the modulated symbol represent the signs of the real and imaginary parts of the modulated symbol, and the remaining two bits represent the sizes of the real and imaginary parts of the symbol. The order and roles of the bits (y0, y1, y2, and y3) constituting the symbol can be changed depending on the system implementation.
FIG. 3C is a diagram illustrating a 64-QAM signal constellation.
In FIG. 3C, a 64-QAM symbol represents 6 bits of input data (y0, y1, y2, y3, y4, and y5). The y0, y2, and y4 bits determine the sign and size of the real part of the symbol, and the y1, y3, and y5 bits determine the sign and size of the imaginary part of the symbol. Since it is easier to determine the sign of the modulated symbol than to determine the size of the modulated symbol, the reliabilities of the y0 and y1 bits are higher than those of the y2, y3, y4, and y5. The y2 and y3 are determined according to whether the size of the modulated symbol is greater than 4 or not. The y4 and y5 are determined according to whether the size of the modulated symbol is close to 4 or 0 from the point of reference of 2 or whether the size of the modulated symbol is close to 4 or 8 from the point of reference of 6. Accordingly, the determination range of y2 and y3 is 4, and the determination range of y4 and y5 is 2. This means that the reliabilities of the y2 and y3 are greater than those of the y4 and y5. In short, the reliabilities of the bits constituting a modulated symbol have the relationship of R(y0)=R(y1)>R(y2)=R(y3) R(y4)=R(y5).
In the 64-QAM scheme, 2 bits among the 6 bits constituting the modulated symbol determine the signs of the real and imaginary parts of the modulated symbol, and the remaining 4 bits represent the sizes of the real and imaginary parts of the modulated symbol. The order and roles of the bits (y0, y1, y2, y3, y4, and y5) can be changed depending on the system implementation. In the high order QAM constellations including 256-QAM, the bits constituting a modulated symbol are arranged with their roles and reliabilities in similar manner. That is, the modulated symbol consists of y0, y1, y2, y3, y4, y5, y6, and y7, the reliabilities of the bits constituting the modulated symbol have the relationship of R(y0)=R(y1)>R(y2)=R(y3)>R(y4)=R(y5)>R(y6)=R(y7).
In the conventional communication systems based on LDPC codes, however, interleaving and deinterleaving is performed without taking into consideration the characteristics of the reliabilities of the bits constituting the LDPC code or high order modulated codes, or only taking into consideration the order of variable nodes or check nodes, thereby failing to minimize the distortion of the transmission signal.
Furthermore, the conventional LDPC code-based communication systems are implemented in a group of two consecutive bits, y2i and y2i+1, only with the reason that these two bits are identical to each other in reliability, thereby failing to maximize the benefit of LDPC codes.